package class_0823Trie;

/**
 * 前缀树
 * 空间换时间。
 */
public class Coding_TrieTree {
    public static class TrieNode{
        public int pass;
        public int end;
        public TrieNode[] nexts;
        public TrieNode(){
            pass = 0;
            end = 0;
            //手写哈希表
            nexts = new TrieNode[26];
        }
    }

    public static class Trie{
        public TrieNode root;
        public Trie(){
            root = new TrieNode();
        }
        public void insert(String s){
            if(s==null){
                return ;
            }
            char[] arr = s.toCharArray();
            TrieNode node = root;
            node.pass++;
            int index = 0;
            for (char c : arr) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new TrieNode();
                }
                node.nexts[index].pass++;
                node = node.nexts[index];
            }
            node.end++;
        }

        public boolean containsPrefix(String prefix){
            if(prefix==null) return false;
            char[] str = prefix.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (char c : str) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    return false;
                } else {
                    node = node.nexts[index];
                }
            }
            return true;
        }
        public void delete(String word){
            //先查找.
            if(search(word)!=0){
                char[] chs = word.toCharArray();
                TrieNode node = root;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                    index = chs[i] - 'a';
                    if(--node.nexts[index].pass == 0){
                        node.nexts[index] = null;
                        return ;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }
        public int search(String word){
            if(word==null){
                return 0;
            }
            TrieNode node = root;
            int index = 0;
            char[] chs = word.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if(node.nexts[index]==null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
        public int prefixCount(String prefix){
            return  0;
        }
        public boolean containsWord(String word){
            if(word==null){
                return false;
            }
            char[] str = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (char c : str) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    return false;
                } else {
                    node = node.nexts[index];
                }
            }
            return node.end != 0;
        }
    }
}
